﻿//给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。
//返回 需要移除区间的最小数量，使剩余区间互不重叠 。
//注意 只在一点上接触的区间是 不重叠的。例如[1, 2] 和[2, 3] 是不重叠的。
//
//输入: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
//输出 : 1
//解释 : 移除[1, 3] 后，剩下的区间没有重叠。
//
//输入 : intervals = [[1, 2], [1, 2], [1, 2]]
//输出 : 2
//解释 : 你需要移除两个[1, 2] 来使剩下的区间没有重叠。
//
//输入 : intervals = [[1, 2], [2, 3]]
//输出 : 0
//解释 : 你不需要移除任何区间，因为它们已经是无重叠的了。
//
//提示 :
//	1 <= intervals.length <= 10^5
//	intervals[i].length == 2
//	- 5 * 10^4 <= starti < endi <= 5 * 10^4

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 1.按照左端点排序
        sort(intervals.begin(), intervals.end());
        // 2.移除区间
        int ret = 0;
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            int a = intervals[i][0], b = intervals[i][1];
            if (a < right) // 有重叠部分
            {
                ret++; // 删掉⼀个区间
                right = min(right, b);
            }
            else // 没有重叠部分
            {
                right = b;
            }
        }
        return ret;
    }
};
